import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;

class Solution {
    // public int[] inventoryManagement(int[] stock, int cnt) {
    //     // 不讲武德的解法：内置函数排序+搜索
    //     Arrays.sort(stock);
    //     int[] ret = new int[cnt];
    //     for (int i = 0; i < cnt; i++) {
    //         ret[i] = stock[i];
    //     }
    //     return ret;
    // }


    // public int[] inventoryManagement(int[] stock, int cnt) {
    //     // 题目相当于是返回前cnt最小的值，top-k问题
    //     // 这里需要小根堆
    //     PriorityQueue<Integer> queue = new PriorityQueue<>();
    //     for (int i = 0; i < stock.length; i++) {
    //         queue.offer(stock[i]);
    //     }
    //     int[] ret = new int[cnt];
    //     for (int i = 0; i < cnt; i++) {
    //         ret[i] = queue.poll();
    //     }
    //     return ret;
    // }


    public static int[] inventoryManagement(int[] stock, int cnt) {
        // 快速选择算法：将前 k 个最小的，随机放到数组前面
        quick_sort(stock, 0, stock.length-1, cnt);
        int[] ret = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            ret[i] = stock[i];
        }
        return ret;
    }

    private static void quick_sort(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return;
        }
        // 确定基准值
        int key = nums[new Random().nextInt(end-start+1)+start];
        int left = start-1, right = end+1;
        for (int i = start; i != right;) {
            if (nums[i] < key) {
                swap(nums, ++left, i++);
            } else if (nums[i] > key) {
                swap(nums, --right, i);
            } else {
                i++;
            }
        }
        // 确定 k 的范围
        // a:[start, left]  b:[left+1, right-1]  c:[right, end]
        int a = left-start+1, b = right-1-left;
        if (k < a) {
            // 在a区域内小范围的排序
            quick_sort(nums, start, left, k); // 不是整个a区域
        } else if (k <= a+b) {
            return;
        } else {
            // 对c区域进行小范围的排序
            quick_sort(nums, right, end, k-a-b);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] stock = {0,1,1,2,4,4,1,3,3,2};
        int cnt = 6;
        System.out.println(Arrays.toString(inventoryManagement(stock, cnt)));
    }
}